#define _CRT_SECURE_NO_WARNINGS 1
//跳台阶——四种方法
//1:44:
//https://www.nowcoder.com/practice/bfb2a2b3cdbd4bd6bba0d4dca69aa3f0?tpId=230&tqId=2357966&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj
//一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
//数据范围：
//0≤n≤40

//1.递归——暴力dfs
//#include<iostream>
//using namespace std;
//
//int n; 
//
//int dfs(int x)
//{
//	if (x == 1)
//		return 1;
//	else if (x == 2)
//		return 2;
//	else
//		return dfs(x - 1) + dfs(x - 2);
//}
//
//int main()
//{	
//	cin >> n;
//	int ret=dfs(n);
//	cout << ret << endl;
//	return 0;
//}


//2.记忆化搜索
//#include<iostream>
//using namespace std;
//
//const int N = 41;
//int mem[N];
//int n;
//
//
//int dfs(int x)
//{
//	if (mem[x])
//		return mem[x];
//	int sum = 0;
//	if (x == 1)
//		sum = 1;
//	else if (x == 2)
//		sum = 2;
//	else
//		sum = dfs(x - 1) + dfs(x - 2);
//	mem[x] = sum;
//	return sum;
//}
//
//
//int main()
//{
//	cin >> n;
//	cout << dfs(n) << endl;
//	return 0;
//}

//3.——递推dp

//#include<iostream>
//using namespace std;
//
//int n;
//const int N = 41;
//int f[N];
//
//int main()
//{
//	cin >> n;
//	f[1] = 1, f[2] = 2;
//	if (n == 1 || n == 2)
//	{
//		cout << n << endl;
//	}
//	for (int i = 3; i <= n; i++)
//	{
//		f[i] = f[i - 1] + f[i - 2];
//	}
//	cout << f[n] << endl;
//	return 0;
//}

//4.算术运算

//#include<iostream>
//using namespace std;
//
//int n;
//int main()
//{
//	cin >> n;
//	if (n == 1 || n == 2)
//	{
//		cout << n << endl;
//	}
//	int newf = 0, tmp1 = 1, tmp2 = 2;
//	for (int i = 3; i <= n; i++)
//	{
//		newf = tmp1 + tmp2;
//		tmp1 = tmp2;
//		tmp2 = newf;
//	}
//	cout << newf << endl;
//	return 0;
//}

//3.打家劫舍（一）
//https://www.nowcoder.com/practice/c5fbf7325fbd4c0ea3d0c3ea6bc6cc79?tpId=295&tqId=2285793&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany
//class Solution {
//public:
//
//    int rob(vector<int>& nums) {
//        if (nums.size() == 1)
//        {
//            return nums[0];
//        }
//        vector<int> dp(nums.size());
//        dp[0] = nums[0];
//        dp[1] = max(nums[0], nums[1]);
//        for (int i = 2; i < nums.size() + 1; i++)
//        {
//            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
//        }
//        return dp[dp.size() - 1];
//
//    }
//};


//输入第一行T，表示一具有T组数据。
//接下来每组数据第一行是整数n，表示n个数据
//第二行是N个数据的初始化，空格隔开。
//输出最大打劫的钱数。

//1.dfs
//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//const int N = 10010;
//int T;
//int n;
//int home[N];//存打劫当前店铺的钱
////从第一个店铺考虑打不打劫，打劫就去第三个店铺，第三个店铺加上home[1]（第一家打劫的钱），不打劫第一家就去第二家打劫，选择2种情况种最大值。
//int dfs(int x)	//x当前打劫的店铺
//{
//	if (x > n)
//		return 0;
//	else
//		return max(dfs(x + 1), dfs(x + 2) + home[x]);
//}
//
//int main()
//{
//	cin >> T;
//	while (T--)
//	{
//		cin >> n;
//		for (int i = 1; i <= n; i++)
//		{
//			cin >> home[i];
//		}
//		int ret = dfs(1);
//		cout << ret << endl;
//	}
//}

//2.优化，记忆搜索dfs
//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//const int N = 10010;
//int T;
//int n;
//int home[N];//存打劫当前店铺的钱
//int mem[N];//记忆数组
////从第一个店铺考虑打不打劫，打劫就去第三个店铺，第三个店铺加上home[1]（第一家打劫的钱），不打劫第一家就去第二家打劫，选择2种情况种最大值。
//int dfs(int x)	//x当前打劫的店铺
//{
//	if (mem[x])
//		return mem[x];
//	int sum = 0;
//	if (x > n)
//		sum = 0;
//	else
//		sum = max(dfs(x + 1), dfs(x + 2) + home[x]);
//	mem[x] = sum;
//	return sum;
//}
//
//int main()
//{
//	cin >> T;
//	while (T--)
//	{
//		cin >> n;
//		for (int i = 1; i <= n; i++)
//		{
//			cin >> home[i];
//		}
//		memset(mem, 0, sizeof(mem));
//		int ret = dfs(1);
//		cout << ret << endl;
//	}
//}

//3.dp
//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//const int N = 10010;
//int T;
//int n;
//int home[N];//存打劫当前店铺的钱
//int f[N];

//从后往前走
//倒序，f[i]从第i个店铺到第n个店铺偷的钱(i——n)
//int main()
//{
//	cin >> T;
//	while (T--)
//	{
//		cin >> n;
//		for (int i = 1; i <= n; i++)
//		{
//			cin >> home[i];
//		}
//		memset(f, 0, sizeof(f));
//		for (int i = n; i >= 1; i--)
//		{
//			f[i] = max(f[i+1], f[i+2] + home[i]);
//		}
//		cout << f[1] << endl;
//	}
//}

//正序，从第1个店铺到第i个店铺偷的钱（1——i）
//int main()
//{
//	cin >> T;
//	while (T--)
//	{
//		cin >> n;
//		for (int i = 1; i <= n; i++)
//		{
//			cin >> home[i];
//		}
//		memset(f, 0, sizeof(f));
//		for (int i = 1; i <=n; i++)
//		{
//			//偏移+2 原：f[i]=max(f[i-1],f[i-2]+home[i])存在越界
//			f[i+2] = max(f[i + 1], f[i] + home[i]);
//		}
//		cout << f[n+2] << endl;
//	}
//}

//4.空间优化
//#include<iostream>
//#include<algorithm>
//using namespace std;
//int n, T;
//const int N = 10;
//int home[N];
//
//int main()
//{
//	cin >> T;
//	while (T--)
//	{
//		cin >> n;
//		for (int i = 1; i <= n; i++)
//		{
//			cin >> home[i];
//		}
//		int newf =0,tmp1 =0, tmp2 = 0;
//		for (int i = 1; i <=n; i++)
//		{
//			newf = max(tmp1, tmp2 + home[i]);
//			tmp2 = tmp1;
//			tmp1 = newf;
//
//		}
//		cout << newf << endl;
//	}
//}

//https://www.luogu.com.cn/problem/P1216
//数字三角形
//#include<iostream>
//
//using namespace std;
//const int N = 1010;
//int n;
//int g[N][N];
//int dfs(int x, int y)
//{
//	if (x > n || y > n)
//		return 0;
//	else
//		return max(dfs(x + 1, y), dfs(x + 1, y + 1)) + g[x][y];
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cin >> g[i][j];
//		}
//	}
//	int ret = dfs(1, 1);
//	cout << ret << endl;
//	return 0;
//}

//记忆化搜索
//#include<iostream>
//
//using namespace std;
//const int N = 1010;
//int n;
//int g[N][N];
//int mem[N][N];
//int dfs(int x, int y)
//{
//	if (mem[x][y])
//		return mem[x][y];
//	int sum = 0;
//	if (x > n || y > n)
//		sum= 0;
//	else
//		sum= max(dfs(x + 1, y), dfs(x + 1, y + 1) ) + g[x][y];
//	mem[x][y] = sum;
//	return sum;
//}
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cin >> g[i][j];
//		}
//	}
//	int ret = dfs(1, 1);
//	cout << ret << endl;
//	return 0;
//}


////dp——递推
//#include<iostream>
//
//using namespace std;
//const int N = 1010;
//int n;
//int g[N][N];
//int f[N][N];
//
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cin >> g[i][j];
//		}
//	}
//	//从上往下归，从下往上推，正序，最后只有一个结点
//	for (int i = n; i >=1; i--)
//	{
//		for (int j = 1; j <=i; j++)
//		{
//			f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + g[i][j];
//		}
//	}
//	cout << f[1][1] << endl;
//	return 0;
//}

//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cin >> g[i][j];
//		}
//	}
//	//从下往往归，从上往下推，倒序，最后有多个结点，需要遍历找到最大结点
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + g[i][j];
//		}
//	}
//	int ret = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		ret = max(f[n][i], ret);
//	}
//	cout << ret << endl;
//	return 0;
//}

//二维变一维，只由上一行的2路径决定
//#include<iostream>
//
//using namespace std;
//const int N = 1010;
//int n;
//int g[N][N];
//int f[N];
//
//
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= i; j++)
//		{
//			cin >> g[i][j];
//		}
//	}
//	//从上往下归，从下往上推，正序，最后只有一个结点
//	for (int i = n; i >=1; i--)
//	{
//		for (int j = 1; j <=i; j++)
//		{
//			f[j] = max(f[j], f[j + 1]) + g[i][j];
//		}
//	}
//	cout << f[1] << endl;
//	return 0;
//}

//https://www.acwing.com/problem/content/2/
//01背包问题

//有 N件物品和一个容量是 V的背包。每件物品只能使用一次.
//第i件物品的体积是vi,价值是wi。
//求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
//输出最大值。
//1-暴力DFS
//#include<iostream>
//
//using namespace std;
//int n, m;
//const int N = 1010;
//int V[N];
//int W[N];
//
//
////x表示从第x物品开始，spV为背包剩余可装容量。
//int dfs(int x, int spV)
//{
//	if (x>n)
//	{
//		return 0;
//	}
//	if (spV < V[x])
//	{
//		return dfs(x + 1, spV);
//	}
//	else
//	{
//		return max(dfs(x + 1, spV),dfs(x + 1, spV - V[x]) + W[x]);
//	}
//}
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> V[i] >> W[i];
//	}
//
//	int ret = dfs(1, m);
//	cout << ret << endl;
//	return 0;
//}

////2-记忆化搜索
//#include<iostream>
//
//using namespace std;
//int n, m;
//const int N = 1010;
//int V[N];
//int W[N];
//int mem[N][N];		//mem定义从第x个物品开始（x-n），总体积<=j的最大价值
//
//x表示从第x物品开始，spV为背包剩余可装容量。
//int dfs(int x, int spV)
//{
//	if (mem[x][spV])
//		return mem[x][spV];
//	int sum = 0;
//	if (x > n)
//	{
//		sum=0;
//	}
//	else if (spV < V[x])
//	{
//		sum= dfs(x + 1, spV);
//	}
//	else if (spV>=V[x])
//	{
//		sum= max(dfs(x + 1, spV), dfs(x + 1, spV - V[x]) + W[x]);
//	}
//	mem[x][spV] = sum;
//	return sum;
//}
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> V[i] >> W[i];
//	}
//
//	int ret = dfs(1, m);
//	cout << ret << endl;
//	return 0;
//}

//3-dp
//#include<iostream>
//
//using namespace std;
//int n, m;
//const int N = 1010;
//int V[N];
//int W[N];
//int f[N][N];
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> V[i] >> W[i];
//	}
//	for (int i = n; i >= 1; i--)
//	{
//		for (int j = 0; j <=m; j++)
//		{
//			if (j < V[i])	//背包不够,只能不选
//			{
//				f[i][j] = f[i + 1][j];
//			}
//			else if(j>=V[i])	//选1，不选2
//				f[i][j] = max(f[i + 1][j], f[i + 1][j - V[i]] + W[i]);
//		}
//	}
//
//	cout << f[1][m] << endl;
//	return 0;
//}

//4-dp二维降一维（正序枚举）
#include<iostream>
#include<cstring>
using namespace std;
int n, m;
const int N = 1010;
int V[N];
int W[N];
int f[N];	//从第1个物品到第x个物品，总体积<=j的最大价值。  滚动数组
int g[N];
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> V[i] >> W[i];
	}
	for (int i = 1; i <=n; i++)
	{
		for (int j = 0; j <= m; j++)
		{
			g[j] = f[j];		
			if (j >= V[i])
				g[j] = max(f[j], f[j - V[i]] + W[i]);
		}
		memcpy(f, g, sizeof(f));
	}

	cout << f[m] << endl;
	return 0;
}